package leet.code;

/**
 * @ClassName 寻找数组的中心索引
 * @Description 给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。  我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。  如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。  示例 1:  输入:  nums = [1, 7, 3, 6, 5, 6] 输出: 3 解释:  索引3 (nums[3] = 6) 的左侧数之和(1 + 7 + 3 = 11)，与右侧数之和(5 + 6 = 11)相等。 同时, 3 也是第一个符合要求的中心索引。 示例 2:  输入:  nums = [1, 2, 3] 输出: -1 解释:  数组中不存在满足此条件的中心索引。 说明:  nums 的长度范围为 [0, 10000]。 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。
 * @Author cqutwangyu
 * @DateTime 2019/2/26 12:22
 * @GitHub https://github.com/cqutwangyu
 */
public class 寻找数组的中心索引 {
    /**
     * 给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。
     * 我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
     * 如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
     * 示例 1:
     * 输入:
     * nums = [1, 7, 3, 6, 5, 6]
     * 输出: 3
     * 解释:
     * 索引3 (nums[3] = 6) 的左侧数之和(1 + 7 + 3 = 11)，与右侧数之和(5 + 6 = 11)相等。
     * 同时, 3 也是第一个符合要求的中心索引。
     * 示例 2:
     * 输入:
     * nums = [1, 2, 3]
     * 输出: -1
     * 解释:
     * 数组中不存在满足此条件的中心索引。
     * 说明:
     * nums 的长度范围为 [0, 10000]。
     * 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。
     *
     * @param args
     */
    public static void main(String[] args) {
//        int[] arr={-965,-674,696,-505,842,-385,-389,-459,-763,132,-310,-789,990,373,375,-707,761,-23,988,-598,703,-902,-582,690,-498,435,-618,124,-347,966,-898,-275,888,-611,940,-292,-341,878,-181,-87,-133,527,-506,-734,191,69,214,-270,-339,-710,456,-733,-667,-23,151,-121,-395,245,59,-458,-20,40,667,-211,-560,544,54,531,853,470,5,-840,-346,919,-226,-340,679,492,435,-531,97,612,-412,149,707,-865,-821,-726,-620,289,33,-811,776,-933,675,26,-281,247,498,-954,795,-202,-59,879,357,340,-467,520,-569,-965,-48,5,870,-485,474,165,-239,263,383,578,-767,204,316,-197,-25,-645,-577,157,15,-44,331,-119,-746,-990,-656,959,810,-59,-674,-672,803,-384,982,-561,374,-541,164,857,461,-335,108,877,-154,133,797,99,-753,25,900,330,486,-631,646,370,-460,-499,-443,750,645,833,418,85,11,-458,-609,-625,-348,-662,967,143,-64,-439,650,396,-802,-774,281,-960,526,652,428,220,-548,-304,297,-652,-75,-262,-762,990,859,239,943,87,-547,239,213,-651,499,-681,-511,199,-550,-897,45,-749,-609,-558,-826,-625,193,901,-926,-175,595,-427,679,-420,-554,-343,911,-292,-428,-394,933,-338,-446,-146,-656,-837,190,420,-459,184,-357,712,-752,-852,56,-743,319,-955,-349,738,-502,-1,-798,815,-816,533,941,-724,-913,919,-122,-731,972,-11,-548,-573,-443,-836,478,-214,937,-279,-127,502,184,487,-754,-993,493,590,716,-292,-74,-470,18,-144,-189,-78,-237,-930,-937,965,82,118,283,511,972,405,199,135,123,-524,525,286,-793,674,-318,165,-343,309,-6,952,-53,-253,-276,187,405,157,-307,93,-258,-980,662,-97,320,-714,-689,917,93,45,-105,-744,-295,495,-139,420,954,342,-317,-432,-62,-323,427,777,-842,143,-465,-149,672,-485,184,660,964,-954,-303,594,946,276,320,-495,818,680,-823,-271,280,-443,120,489,295,-450,-895,190,627,-606,11,-280,-482,-103,-127,-130,-67,320,-957,565,263,633,229,371,-515,-58,-586,-432,991,153,647,-442,-566,128,576,390,254,-937,712,989,-953,728,867,-666,-346,530,627,556,-54,-58,-654,-577,-805,934,-520,-382,-158,597,972,-251,312,-146,69,727,-702,-532,-482,498,138,-947,854,-961,-915,-23,639,-970,784,945,-1,-998,-926,-182,523,-918,-856,202,764,-81,-147,-434,-349,-686,-628,47,-27,326,-859,-167,132,-469,-895,390,145,115,-639,-163,-578,186,210,920,949,-595,-700,335,873,433,-392,520,-127,495,320,-353,914,114,470,-964,949,621,-264,-176,-273,-483,247,-829,-911,776,-967,-133,-242,-571,98,779,-752,-510,-270,-899,-247,-932,491,-290,-745,716,911,-64,25,37,549,-669,409,473,-32,-613,849,-402,-647,-313,67,-910,-237,231,-756,-925,52,800,535,983,259,354,-209,-386,448,535,669,-49,-272,-264,707,379,857,650,881,781,-323,867,593,-378,-185,462,-405,981,99,132,241,551,-21,984,720,814,217,-727,-958,-809,652,116,-634,485,47,297,-89,186,668,60,467,155,-516,-994,847,708,-840,923,-242,660,142,-166,-863,672,593,869,217,127,48,-355,-244,880,980,-655,-787,-842,498,-77,-429,858,776,-991,-793,210,-876,593,664,345,-545,-619,-894,-350,497,-5,-882,181,-662,-542,-528,137,-386,897,888,-436,-787,22,708,773,-751,78,237,341,-327,-471,576,-310,-549,789,-619,-885,-303,448,261,-958,824,-697,-289,390,75,-314,969,-16,-115,-458,-670,-868,200,578,-690,-894,-127,587,267,-200,848,-104,-771,908,623,433,98,-997,631,879,-498,-283,210,689,-259,-35,769,-626,-596,527,500,-940,-881,-216,114,-336,210,652,199,-298,-894,-419,390,-199,446,-753,63,893,309,-14,-613,-615,-273,216,-167,445,-317,-201,217,457,78,761,49,385,-394,-548,746,-78,498,-795,164,-292,-849,-37,-65,514,-95,789,-35,346,566,-451,435,-881,157,713,169,-889,621,-604,-840,-950,-544,850,-206,-840,-126,57,772,-394,382,330,884,-413,414,364,291,-628,-913,-470,252,-259,731,385,721,859,-985,-99,433,668,-138,96,-638,576,309,356,652,-354,950,-596,-329,-359,-658,832,-133,298,-994,188,-868,-488,-447,-461,816,796,97,-280,-37,838,-421,333,469,-686,603,345,249,-967,726,422,-390,340,-526,18,395,537,-783,109,-397,-137,471,-175,-748,541,-444,-258,577,178,-456,883,926,-86,-482,571,-18,681,4,614,946,738,75,-768,916,-994,405,722,-783,-828,-187,706,89,-580,-991,822,-779,145,-260,-85,-460,725,-208,174,397,-341,-49,-510,11,804,-780,-477,973,985,-78,-287,-684,-29,940,732,853,-674,-282,-704,-245,171,447,-304,373,-727,-818,-936,-4,-579,-570,678,-517,-601,647,-449,-603,369,-80,494,-714,721,588,-880,-779,-811,-834,393,-364,-707,-963,352,830,97,676,-297,-694,812,-992,-324,511,595,834,-309,-553,580,-993,69,-219,-628,927,184,-745,905,911,-915,920,933,413,433,753,826,829,279,150,765,226,-486,-723,415,-36,737,-970,567,728,545,20,-286,-481,-671,195,-430,-636,185,-897,8,987,-593,22,-390,-540,878,777,-574,955,-904,-702,-514,-803,-659,-982,582,-35,-410,389,-76,-931,-503,704,575,-352,391,-712,849,590,996,-192,-6,612,713,129,897,454,-858,-481,903,185,-546,-9,-574,-267,-121,451,339,-387,142,923,-840,630,837,755,-526,333,-686,-550,206,116,-70,660,-799,-40,-728,-419,358,-816,-302,-606,874,306,604,-997,156,-561,-883,857,-640,39,686,55,734,-442,204,41,58,-364,49,45,-550,-474,308,372,547,269,654,-857,177,565,-664,-867,474,498,609,251,-801,-31,197,-233,-713,-21,-17,728,901,-978,157,-792,-439,931,-417,871,392,438,903,-419,-662,438,-377,-61,87,-367,775,-611,-784,532,-183,963,135,868,-255,-480,447,557,-944,394,-778,54,-204,-399,-877,-94,545,-800,-177,-453,-161,-64,-906,609,-589,476,702,530,829,-996,959,-696,160,-908,397,-113,229,658,860,149,209,-791,583,144,-1000,-772,-122,-45,276,-167,318,74,-172,-384,-413,891,-673,-929,-128,-3,101,123,-503,509,-799,-385,34,162,370,711,-177,-838,737,-305,-987,87,-990,843,-282,-374,241,57,288,775,755,-331,602,599,122,845,142,437,607,-240,-999,799,24,-675,-913,553,144,-162,-114,157,640,247,536,-374,160,301,711,892,463,900,-206,-843,292,-579,-374,-555,443,406,-899,825,-88,-837,191,-608,-799,427,659,-501,932,917,230,-109,836,-282,689,-849,458,46,-725,582,142,-898,302,166,443,-507,372,552,21,633,139,-649,458,-177,731,153,4,-920,424,-526,-277,632,918,763,714,-62,776,472,496,364,767,882,415,344,-786,-987,-200,509,-872,510,-882,648,-454,-624,-980,15,-304,686,-932,-98,861,-656,-240,370,-575,492,638,-828,-120,475,-460,-644,-482,668,-802,-363,-181,-539,521,216,-387,960,-788,512,-95,-516,689,-47,571,-239,-931,312,-678,-894,274,819,-782,-260,718,-401,234,824,738,234,363,-237,687,-544,165,336,207,-681,-267,488,-586,640,639,-905,523,-424,577,212,-154,-138,479,-843,-225,-47,206,-4,-538,-196,-661,166,874,-51,400,89,528,-646,223,-374,-460,-637,794,-960,315,488,-311,-728,301,-382,-593,896,516,748,-81,-243,339,52,571,11,578,686,369,-663,807,291,-167,396,297,645,452,-733,-470,392,214,-725,-85,117,-487,900,-277,-548,405,-789,625,-131,-819,885,-665,156,-127,838,-271,281,709,-428,837,852,-84,-114,-797,-865,-764,-15,157,449,11,-152,78,27,-199,142,826,-420,-638,-64,-874,-705,452,860,-803,-673,-113,-397,-722,-975,-954,983,689,-733,242,-196,-824,729,576,63,377,-127,-593,644,300,594,-68,-12,-660,-523,451,-308,330,-484,-537,275,491,-173,106,252,786,397,-666,-550,-19,281,407,-352,297,264,973,968,-894,856,-62,22,456,969,-428,267,66,-64,-66,-756,943,-113,578,484,294,-303,949,-565,829,647,974,-445,-273,691,-371,102,-282,-672,-102,532,77,900,115,862,683,-700,-468,732,797,207,368,-997,499,-346,762,-819,306,-823,-645,617,779,949,413,-90,141,-893,-422,-429,502,-474,-338,-857,684,-311,375,-500,-25,768,-143,148,-869,-553,-237,274,254,-421,596,-463,625,386,-91,-945,927,927,-804,-199,891,-938,-471,22,-706,580,-807,607,-47,248,340,905,767,-837,793,-244,145,572,-300,-69,896,-517,-350,221,-461,-110,-117,-71,468,-443,972,-595,-238,326,-421,-70,-844,843,-377,600,-373,695,1,186,-889,-685,-98,-200,287,-507,538,-639,-446,538,-827,994,1000,715,227,514,882,427,-128,151,-355,95,-989,-736,815,108,-986,756,841,665,820,453,374,-676,-436,828,-522,-935,274,823,-822,-153,-609,-91,-275,-553,-891,-831,-475,-208,490,-663,-871,-833,41,40,-812,214,-978,-995,-418,667,564,701,204,841,581,137,-869,-194,968,942,73,-512,-240,27,-91,770,-840,708,442,415,115,327,134,840,695,-18,-783,470,542,136,163,-326,-222,-974,665,537,16,-339,-835,181,-58,-395,-184,-743,391,-688,-490,-147,510,-652,-466,-312,937,178,-21,-245,818,681,-616,-322,302,-764,593,-287,7,305,868,464,-109,287,116,-477,-569,567,118,397,-935,525,-568,959,-251,-652,717,967,429,391,-962,944,-112,166,945,-377,-535,-890,189,-855,-931,-918,-397,-553,-255,433,667,-654,7,-746,121,780,376,-38,112,-798,823,-903,-616,340,670,-586,935,-900,4,-536,-85,-431,-853,-425,-748,-278,384,185,759,566,-524,-526,304,295,218,-161,-42,6,150,251,-119,179,1000,-913,-920,338,935,183,259,483,393,-674,876,-609,414,528,898,-938,239,849,-408,270,690,51,550,-698,-462,-454,994,38,-152,-786,-304,-879,-885,-436,-152,-408,-882,-477,444,-211,-47,-814,-167,-235,403,558,8,-362,171,446,-300,498,133,167,105,376,407,595,-21,-259,-123,-114,-222,-848,-264,317,834,87,-98,-386,502,962,873,597,-98,-905,-381,-598,359,-555,973,-121,-77,204,255,258,919,-706,-389,34,-289,-959,-856,-14,641,2,-585,-87,-353,513,981,-581,-381,-888,-66,267,-591,274,-321,939,331,-998,978,-900,-143,-400,-956,336,372,-166,179,698,-213,-353,252,626,-889,836,38,412,-877,409,-958,623,808,348,62,-533,-271,353,-23,-436,-30,-57,-828,-297,621,-655,405,-519,-493,-441,-645,364,988,144,-309,461,-390,759,-123,-483,-785,-821,643,33,-292,-607,601,503,-276,-723,642,261,-983,-203,404,-684,-634,697,301,-918,993,936,731,25,-452,-463,-959,-166,-881,-599,814,-136,-959,-501,-925,-66,-768,105,-645,-180,-989,-2,914,-580,308,13,-435,795,214,-333,337,834,732,-575,-797,-574,-59,-785,617,-484,-926,-734,838,345,-78,963,333,813,47,83,-243,751,412,-520,976,967,382,-526,-406,847,-846,523,599,-687,-342,13,-878,-326,-926,690,123,752,573,-404,-620,-743,623,691,724,986,-96,-715,-745,227,-995,563,-402,-716,-399,631,-735,446,300,-155,54,-387,630,-443,-501,-277,-279,573,-707,532,571,473,664,-395,-508,695,32,95,345,-856,-518,-145,506,139,41,787,-422,-440,-259,555,737,66,302,217,-668,-168,-294,999,-111,-332,273,-690,598,17,-158,-451,681,-253,-861,453,872,-80,-945,855,881,821,392,-351,594,-968,-802,651,-749,-258,31,-937,-38,23,288,-641,-812,-108,583,576,392,526,-941,184,-759,156,-138,439,-827,401,-449,-420,-258,-217,-34,187,-716,-118,-661,-930,-898,386,605,-489,476,934,-5,123,-709,-497,-773,-494,152,-835,331,971,277,-614,126,-248,234,-370,63,699,-834,184,-778,863,315,-678,707,267,807,521,-264,336,245,29,-627,320,-517,-215,559,-783,-748,-25,775,448,-627,256,-959,941,398,-703,728,-807,721,-855,423,-290,317,165,201,194,-940,427,643,302,-958,733,43,-101,153,939,-325,-312,-193,100,-735,415,-103,126,900,162,-79,61,-707,722,-330,-425,-245,-137,511,947,-154,-569,404,-724,856,64,776,-513,-878,-837,-323,-803,-399,772,102,469,132,173,263,509,408,-268,-307,58,-912,-752,505,-626,325,623,329,806,-810,42,812,228,303,-81,629,764,986,792,748,-578,-411,-703,935,-604,-656,-80,471,229,-227,-137,-360,322,780,-400,-528,28,-405,-498,-514,-316,-173,-862,-833,-904,-412,148,285,-732,79,348,459,-562,920,225,975,645,574,455,-271,955,237,-309,534,-42,492,-134,860,718,-678,336,82,919,-561,-37,-455,191,940,833,-87,410,997,-307,-190,831,-125,-633,-519,-262,414,-993,-25,-738,224,-333,-390,932,277,691,-40,534,795,608,619,-637,343,-262,877,833,-799,-15,-426,281,916,-459,898,-388,-474,312,-481,979,725,-204,-971,-626,-578,-867,318,-617,-855,-595,954,-766,-851,-299,63,467,532,-324,219,-260,261,-77,-825,-600,-525,924,-971,-332,865,765,-197,487,-421,80,-24,-691,-767,-221,-217,-566,-469,-183,-910,923,-679,-210,-549,-288,-655,-705,-929,-416,111,519,-323,467,100,162,851,-887,-253,-522,3,995,403,335,-37,-61,-430,487,412,962,-511,269,527,-415,964,-879,836,-581,732,875,508,55,-22,795,760,-664,10,-810,-744,907,237,976,599,-196,411,-680,-720,274,-82,166,-427,-455,914,593,-778,462,399,-886,565,349,-858,974,526,579,-476,-566,287,999,823,301,-832,-46,551,198,-39,-601,806,457,968,-591,-297,186,-899,-819,872,-351,788,-43,-912,581,521,204,994,-775,-752,-771,397,-733,-393,-832,-489,-641,276,280,-394,866,42,-228,692,391,315,292,-969,449,911,-173,-415,-140,383,676,25,996,346,125,553,-725,557,203,-804,94,-129,995,-446,-719,-288,-697,455,-783,-560,956,461,469,596,-593,265,823,321,259,635,551,-921,260,-554,-618,-953,-946,-874,-270,33,606,-692,-602,-95,-698,263,46,708,110,-191,-240,-519,-142,940,974,-910,912,-900,524,952,-303,-428,-198,375,-880,-982,482,334,-285,-658,-71,-196,-192,-47,-879,-806,496,799,826,74,959,829,639,-962,325,89,527,-392,-334,536,-30,250,991,-797,824,431,-346,-865,-689,-418,-929,252,-483,328,411,938,754,-746,-27,-794,61,414,693,849,-734,407,53,-288,953,170,-830,-860,431,803,-382,-296,36,-322,-824,-154,999,-862,148,-597,74,618,840,-75,-754,-45,-79,-375,-652,470,-697,703,632,-726,382,336,-656,903,250,722,-114,-509,-306,-565,8,630,417,-25,609,-904,-595,612,509,531,835,-329,-753,-964,-283,711,-836,91,164,-617,-513,588,415,-482,995,-223,-881,-995,-346,804,435,796,-874,-284,148,559,-655,-576,-79,853,808,-741,-667,-207,732,237,601,79,231,759,-387,-468,438,513,-742,818,631,-6,367,-488,-400,-34,-860,-373,-96,-406,54,-688,-865,944,817,-474,476,305,-470,865,-892,187,77,467,317,-915,-616,-863,154,-512,635,462,519,-700,223,-193,-670,-250,736,-82,125,734,-742,393,-94,863,-3,93,8,556,-11,387,561,-212,-501,-580,639,455,-56,356,152,-829,-873,-178,-577,-173,-579,-139,505,-349,747,731,-49,-60,-179,684,-19,548,556,683,790,316,-878,-372,-250,454,-909,732,-27,-176,-906,371,794,-722,-221,-314,-860,-321,-422,-119,-657,603,915,449,284,594,-673,413,101,218,-732,400,-501,764,-182,557,937,996,818,-267,-739,635,-314,-566,881,-822,623,592,611,510,-874,817,501,405,855,-705,905,-216,897,-424,224,397,621,-456,-373,-780,617,381,508,-208,758,-869,-593,-465,-600,784,207,498,-156,611,-626,-656,156,-782,-710,-563,-436,176,-508,-571,933,-656,365,-899,-662,-380,-865,722,149,555,346,340,622,503,-502,-516,-295,782,-773,554,-161,569,837,121,-696,962,-97,793,921,589,-397,296,645,-138,-288,578,665,-935,780,668,-125,545,519,-759,-97,-188,-991,-777,443,900,706,339,-671,185,144,899,-165,105,-235,-979,-74,-138,-593,120,759,785,584,961,248,-55,322,-473,94,34,440,-466,-381,-589,-399,-367,687,947,-446,223,-136,-515,-949,885,-200,779,-112,962,-196,-597,200,306,-163,-656,751,749,479,128,-625,249,967,-522,-833,-54,206,-694,-546,497,554,-189,463,-839,-606,-639,-690,-844,-595,-490,717,706,508,741,773,-138,-327,-158,-376,-283,481,493,-286,-436,-421,19,713,-763,325,-185,-983,674,948,-258,-282,830,534,411,-344,757,628,327,-299,497,737,434,759,-849,666,367,-597,-390,-241,331,-405,-11,-984,-645,456,230,-940,951,3,962,338,756,-837,200,-861,-568,-587,448,-81,126,507,-773,860,476,-700,-574,-230,468,-297,-346,584,796,-783,315,-891,985,313,-70,775,116,43,36,812,-788,624,645,-323,-912,701,222,691,-158,-491,-610,-890,-65,596,48,420,-836,40,651,-268,-964,-86,-430,344,73,-573,-841,207,910,-300,-404,610,419,692,-693,47,337,614,950,-250,506,-153,-646,401,60,-103,-298,-339,117,-840,-57,-250,791,-448,-597,-102,821,238,460,946,837,378,258,941,683,944,-996,-402,-260,-109,-452,-33,176,483,-835,479,-322,-884,-740,496,635,-201,122,819,333,-131,-133,709,-841,-960,-277,616,59,-14,920,-295,-341,684,446,700,-95,-324,-549,-108,145,-682,546,434,-378,589,716,188,940,312,-60,-829,-620,541,-289,79,855,-420,-811,426,577,-572,547,-1000,-802,-934,-376,844,-16,165,-893,741,-649,124,-932,301,-752,922,584,-295,-904,-377,488,-254,578,-897,520,-17,307,-858,-264,90,-680,783,700,14,550,58,-663,-789,-94,-646,817,-125,972,-216,-814,-246,-19,3,975,258,-625,-267,-699,587,829,641,-823,-185,829,-746,-409,-594,-868,21,749,-40,-860,388,-449,-280,-720,-339,384,-288,-113,-614,390,541,752,729,-526,-75,-329,-528,-654,657,-245,911,-452,-438,557,-114,97,-86,93,938,390,430,560,682,-927,53,-925,831,-673,-406,516,898,994,439,-518,-462,-915,815,662,-714,-775,497,-207,559,402,-290,-286,359,445,-942,-805,776,439,-619,-516,20,-304,72,810,-535,435,-105,348,-967,909,569,-34,168,-634,719,694,695,593,-58,218,-896,662,-44,-487,-126,-856,732,-77,-546,142,-370,607,583,-66,683,995,-888,821,-454,-622,622,64,630,-74,-326,-343,556,542,907,-116,-171,-352,996,-572,-312,-362,768,139,-315,-768,850,-35,366,-675,611,-146,-755,-21,-330,615,-100,664,800,396,281,611,160,-128,909,360,-979,-449,-334,-994,-878,702,904,91,499,-970,663,110,-919,21,259,890,-879,392,-373,558,-403,889,-872,432,-181,172,-869,249,167,396,-105,841,-618,469,-329,-88,563,-689,-911,-265,-541,724,-461,-304,470,804,240,550,138,-571,-634,838,-146,-996,-803,-270,919,801,402,906,-94,387,-404,-965,419,58,540,903,401,-452,140,-841,-479,320,-596,361,306,-222,667,913,100,415,-987,984,400,-601,-839,545,484,-854,490,-797,-613,370,695,711,-90,667,-244,332,967,223,-100,-743,-887,-28,-10,852,-362,129,692,583,-932,-523,-350,879,-498,71,-329,-752,-120,-797,273,-5,-65,799,-835,-584,628,578,-906,-436,750,-193,716,-976,-991,727,-860,-637,611,77,-504,-373,68,984,-731,661,342,735,-871,-555,-213,898,-304,189,100,733,811,-303,-881,-433,-916,771,-584,-685,92,-17,-927,-329,327,-431,344,-143,757,414,850,443,-102,-506,857,-492,984,809,-486,303,997,-677,541,-831,-812,-428,-684,-383,275,10,-531,930,948,-499,328,882,-793,-614,-268,-901,-925,810,-435,-521,-100,-886,18,467,-39,-935,-343,463,936,-106,-371,-718,-720,644,641,-950,600,975,-181,642,-20,-367,-393,-709,785,-524,451,412,854,617,-419,133,-146,-693,924,615,-521,-600,-3,-840,-603,-78,16,-536,-419,132,-130,956,-900,608,-370,-185,458,-451,883,97,-21,168,-127,-634,-843,121,-401,793,-185,-833,-258,-295,610,437,508,-551,906,971,239,-431,343,-911,-134,-98,-419,744,-552,782,-743,-372,-820,-127,856,633,-352,270,-33,488,-536,-125,-329,-55,-95,-306,471,861,67,-587,518,327,-410,-476,-812,-351,300,-633,159,469,784,-807,-599,443,152,-559,-459,-239,-597,-932,51,-323,-413,247,-62,-563,-921,-451,78,784,-482,-854,-388,-520,-712,849,450,-797,999,-899,-553,509,-859,529,-551,-802,-774,-999,637,373,873,473,-769,774,594,-916,-575,605,289,-735,-440,-142,427,325,817,334,149,-601,-650,-802,-244,-837,-182,913,-111,214,-881,815,201,199,-945,849,-223,173,-513,344,495,-375,557,-253,-771,114,-358,-926,661,-382,890,-958,-615,112,27,-976,961,-913,-83,-959,771,256,64,-170,599,658,917,845,180,-221,458,-934,-790,-72,992,704,-400,763,-170,-532,708,-368,-836,-63,-257,-461,260,375,227,-609,-710,30,853,-814,-503,923,-220,-286,-230,-149,-313,-533,-170,866,177,18,-776,580,596,-474,598,833,-658,-260,253,738,415,-737,303,716,-695,469,-340,225,-105,-156,-216,-496,491,-592,-615,528,-637,932,8,410,705,129,-896,837,-396,175,-288,317,-910,901,710,785,274,978,272,-304,-604,-819,-128,-67,-120,60,-440,195,-606,521,-890,834,982,141,865,-309,-711,-441,-404,-30,322,398,396,497,-528,-334,751,543,-775,-83,-375,258,581,-334,111,-636,668,-512,-476,769,-809,725,475,827,-341,70,11,-507,-755,-255,870,508,261,-124,-33,289,581,554,902,384,862,-289,644,988,990,-825,366,43,-478,-652,825,-83,-749,-338,432,-677,-418,575,-140,-287,-124,279,12,670,598,-83,-259,-769,-799,-960,-241,-471,558,444,-295,-826,294,-563,459,-390,373,357,106,519,-928,360,601,-638,352,937,199,480,791,531,-329,-950,-502,-234,-843,413,781,467,-196,862,-111,651,153,41,-379,186,-424,879,80,466,-60,-298,-925,-278,106,-897,233,-149,350,-712,-939,-66,512,-217,-828,-620,-514,-954,288,216,-933,489,-822,-51,-826,-720,-711,-374,-486,-620,-203,633,-456,868,964,-221,-781,-233,472,-895,-450,-345,979,273,641,362,481,978,991,-713,-227,-92,314,653,250,-86,575,862,512,189,825,757,716,-714,-643,-451,-491,-416,725,-4,235,437,-411,-779,670,-732,-30,-85,184,-304,-530,303,-526,-899,-473,-90,364,-146,-102,504,983,212,-148,-588,-20,928,-592,86,615,58,139,898,-988,-515,504,171,553,-99,-891,671,-51,120,-846,-178,-730,699,-820,-493,601,-902,800,-916,-3,613,-949,-951,765,785,411,-699,810,816,386,-310,-81,283,540,-725,751,-182,697,903,-494,-780,109,-775,782,31,241,-745,51,882,-642,-279,-282,89,-754,110,-491,960,134,62,-783,-56,-721,166,750,302,-117,497,838,-887,577,-304,-190,820,-599,689,-605,476,-612,-442,302,-314,282,-231,-513,-229,614,273,-95,725,-693,-623,-615,237,-741,-151,-885,654,926,111,-544,-252,430,-435,-59,374,585,-862,217,-368,121,-199,25,-515,109,-20,-426,-698,410,-438,-367,461,502,-336,-353,632,-95,505,374,-257,-999,217,432,-844,301,-477,605,104,818,-135,-293,169,224,-408,746,356,-590,639,618,553,921,727,239,544,-159,401,509,-807,-743,-543,447,-824,95,36,802,-426,-40,975,-365,-368,833,270,-865,521,583,539,-357,610,-145,-1,286,594,235,571,-697,-530,248,-181,668,710,972,195,-155,964,717,697,-519,-670,400,374,63,-594,743,726,668,917,-39,304,864,838,886,-95,426,974,-510,-300,520,71,139,549,999,-686,885,-644,620,-66,-994,126,340,819,815,788,-501,-873,411,-439,868,-474,169,-407,-225,-717,436,964,-729,-496,941,-11,277,-586,363,256,666,706,801,551,-494,-999,-564,528,-299,-448,-712,402,-27,339,-884,-564,951,514,-64,-453,-533,-726,-718,-523,-615,21,182,-477,-248,569,-115,-671,-72,732,-739,-10,-976,103,-407,178,-520,-929,562,-661,-238,-912,273,930,-221,-867,228,907,-659,989,171,297,-69,-711,-291,-137,983,-743,-762,-468,226,-740,841,162,540,-635,-7,971,-196,-640,-154,-817,867,491,569,212,554,48,-299,-681,213,-550,130,-759,-949,-465,684,605,250,-636,-585,-482,-670,855,-778,-870,558,267,142,737,839,337,826,874,-806,-810,-223,204,68,986,57,-253,15,-385,-333,237,616,17,463,-166,391,251,-840,-334,258,385,591,-207,386,684,-240,333,-18,-525,67,-742,-849,-57,832,664,21,978,162,570,963,507,-968,221,269,-373,-433,-777,-908,442,-323,458,-94,-673,-400,252,-26,163,-392,340,206,-619,-108,-41,-987,-462,187,118,-699,-713,-790,-694,-791,-599,-123,386,463,67,-990,-475,786,686,6,-835,800,536,556,-818,-639,509,806,861,721,431,-359,-799,534,735,75,-658,747,625,12,117,-282,345,378,324,-38,-723,-486,-681,205,835,412,-427,-47,-729,918,-388,551,-277,-400,-381,513,535,842,995,-812,103,244,-826,369,892,-340,330,776,826,-446,587,690,138,-663,-546,650,-135,14,-978,688,17,128,-604,563,513,-115,637,-996,913,596,-603,-525,475,960,-654,13,-626,-171,2,995,38,913,-769,611,183,509,869,-589,911,-572,-752,218,694,390,-907,-888,601,-368,-143,-371,189,-389,604,-362,523,952,489,-913,-902,-184,-19,834,872,-888,337,-116,-135,810,-159,-329,338,397,140,231,-357,-572,-792,397,718,699,-73,-760,751,-558,-589,244,17,-36,-997,-873,-420,972,567,-363,844,-395,23,136,890,407,840,-799,-22,-566,826,556,-166,556,-662,-405,-549,-292,-538,131,306,-503,-987,-142,148,-717,429,-462,-127,577,-36,-893,-152,-340,-97,-958,-544,-671,682,206,-667,159,775,-180,460,274,345,621,-470,-428,877,191,368,438,-78,-590,783,968,208,901,-300,-361,856,-353,-150,668,-950,-554,-819,33,-562,420,793,8,-252,63,458,911,-644,744,-464,-17,139,-478,-436,328,605,833,-21,-779,-717,546,987,-757,-199,426,-925,996,-29,679,-912,60,-618,506,855,-717,648,-826,-517,784,-191,141,-682,80,-442,764,546,980,-588,-830,-860,547,5,400,-395,-591,-876,36,894,-525,-138,125,-143,-458,-490,609,817,-509,347,298,-38,620,82,504,51,-325,-945,-862,-605,-487,-83,138,-606,531,412,127,-462,709,828,595,-68,-309,-975,-576,548,345,94,355,375,791,368,346,980,-465,-179,-318,647,128,213,-180,220,-523,710,-121,885,-744,51,835,-91,-948,-541,-71,543,-636,518,32,500,547,-596,-995,996,98,-156,-399,47,-889,-589,-291,521,-359,351,-434,94,-695,-81,-16,104,-465,-781,119,-482,231,438,58,-314,-784,482,523,-209,-461,583,864,-626,394,-566,510,-253,154,808,-774,-812,220,-736,251,376,-434,-430,-813,870,464,525,953,691,87,-232,-367,-229,343,-538,579,38,-501,144,-332,-48,-939,391,649,51,-380,-134,-330,-538,632,531,720,-697,-255,-877,101,-341,-178,-664,-991,-305,319,154,-321,-179,-662,27,898,32,885,456,-189,836,-977,-192,-720,-330,-186,-63,249,601,-615,872,-106,-608,-547,-745,-869,54,-106,679,301,537,974,-80,-531,-716,-621,754,-910,490,-916,-852,-224,580,29,-29,-730,421,833,-986,-502,-92,21,643,749,-834,-827,-812,555,-821,598,100,913,425,343,-41,388,400,825,-953,-838,-692,911,745,-267,802,-840,657,638,-317,-944,-290,960,500,954,-718,712,768,813,908,-550,-108,652,-98,985,-410,-803,302,-144,-284,670,-362,-81,36,481,377,-360,-577,262,-925,-335,-223,927,841,-144,565,826,-286,187,-670,771,-322,852,-767,545,-121,261,-312,420,754,645,635,-402,397,-287,113,637,-595,226,784,-475,-528,229,550,758,65,340,-296,706,635,-623,-401,325,988,65,487,-994,-607,-397,-40,-309,585,-343,724,196,570,990,395,581,-302,-582,-29,896,764,533,-842,700,-599,409,-964,-316,834,705,27,-424,-136,-442,-433,685,774,-62,-712,-85,-435,-311,-420,-788,-965,317,-783,648,-662,-387,-314,514,513,1000,-56,637,134,747,-314,-982,360,284,-15,-21,407,-192,124,-693,869,269,-669,721,-340,799,-834,-384,622,-446,-580,-393,75,735,-492,-22,-590,-388,-419,912,709,-955,-303,853,-272,807,949,613,-623,-794,115,-791,741,327,176,668,-101,933,741,-929,928,-361,-420,-222,372,741,-117,-758,-269,828,-951,683,-964,-910,791,890,174,849,-887,-657,246,-318,238,978,324,-185,768,-567,-275,405,-223,810,-736,457,-176,771,85,833,55,-320,-711,357,-982,968,719,593,673,42,296,203,-492,877,246,-490,793,-455,-339,-632,-861,-128,-47,588,535,-63,489,681,-658,-18,-149,579,-52,263,-717,-823,-819,90,513,-164,-645,-227,-870,-106,-482,470,329,38,-233,-971,-406,-863,965,-529,476,-682,-85,-553,363,963,328,-716,-555,-176,710,458,-801,-863,695,508,-93,-203,-55,-228,205,-173,-195,-124,991,917,-392,-223,423,519,-555,-256,526,565,-619,-685,-459,-850,-464,-189,653,341,723,356,574,38,-59,-407,815,-886,208,403,352,-888,92,420,-115,862,708,634,856,300,-899,16,-814,-627,-451,-246,-128,149,512,620,278,487,470,-782,-862,-351,-308,620,-87,703,-635,-411,-958,620,-938,-575,514,620,279,-401,-706,548,336,2,-105,774,-850,725,-253,421,5,335,799,-784,420,-847,117,174,602,128,-317,-9,644,284,650,-301,-747,-212,606,-684,-267,764,-252,-508,446,25,994,853,455,-177,-740,801,-565,403,310,-568,-289,31,354,-399,853,-673,-203,698,123,-144,509,730,864,-704,-275,332,-376,932,-310,-750,-956,-534,-607,856,834,-581,826,852,-146,450,-316,707,704,620,-56,-460,-189,-552,152,990,758,-903,-848,742,708,291,663,-707,-25,239,-890,-981,153,541,133,-38,-203,-191,358,336,-398,-812,385,274,68,433,75,-310,36,-56,-450,-6,565,-727,559,921,480,709,-150,212,979,697,562,931,445,-271,462,344,201,600,40,845,402,251,-896,-515,231,-122,-43,-886,110,289,-554,-656,548,492,-834,-968,946,890,-693,-904,-699,-9,790,406,-485,283,-138,627,294,582,-769,-490,507,36,-837,-103,975,-903,956,-937,184,-578,626,978,-435,937,429,-776,854,101,-193,370,-678,400,171,343,-803,892,-616,-530,75,788,-639,-116,851,295,-123,-238,829,-821,-927,46,27,-473,-511,-373,73,881,279,-645,577,-466,959,33,253,-990,39,-654,28,-761,959,320,668,-675,-252,-564,-954,-396,259,174,747,851,156,245,771,-656,537,-961,793,-799,-708,127,-409,954,462,193,718,-315,357,775,-690,-363,-738,-621,-77,-362,203,-536,170,-729,654,-33,51,-164,535,-634,390,-582,-598,-290,-699,458,-257,168,112,736,334,805,-803,-39,-811,-204,551,182,642,653,-374,424,931,-941,750,204,697,-840,455,255,607,-145,305,945,-279,15,-174,-651,310,-785,-792,-693,-474,-881,819,-914,121,780,-298,717,-709,-107,-550,-272,-539,-50,-575,-639,-782,-139,827,-672,-31,624,872,-446,-347,240,461,955,-97,433,-614,-976,237,-797,-950,31,-348,-184,-164,903,-492,907,437,-913,-780,833,193,452,-987,-183,609,782,-618,787,-314,-345,457,-417,-167,-186,-69,66,834,-430,443,836,-597,-506,359,419,919,163,214,-197,56,333,108,89,444,709,-797,-562,795,-223,-459,-371,-802,724,167,-994,-492,564,984,-332,806,-943,-844,9,960,-211,184,-239,985,-341,-440,443,332,982,9,-924,-457,-302,338,-430,604,710,-816,-502,937,951,-981,225,559,95,936,320,806,-299,-947,967,-717,995,-857,505,-262,-564,539,122,472,-417,-749,893,668,295,211,959,-250,62,-837,-523,-938,-951,138,-866,906,822,-788,817,-41,492,-535,2,-910,469,333,875,-532,580,-655,932,-240,486,245,145,682,313,-32,-979,-371,-742,255,-975,-547,357,727,845,-527,-310,-876,937,-354,-637,-186,-69,341,-424,-40,-295,-103,962,167,-814,959,-507,-429,158,565,-967,-610,860,-638,18,-596,166,708,66,565,511,265,-605,-532,8,-99,673,381,77,554,-144,283,-662,-168,179,607,212,591,167,-205,24,-593,231,-757,-612,-817,295,583,778,965,-275,-57,597,947,965,-141,-355,17,-591,812,716,-184,-176,-751,837,-41,135,-385,364,-698,827,-520,-923,-738,-41,-90,998,354,266,-372,668,-144,-713,902,-435,-376,-584,-499,936,-16,347,-955,-728,530,-585,-831,-981,-447,-845,-100,973,786,-924,-157,791,-482,89,423,-33,-610,906,-133,435,934,472,-664,35,-240,-166,330,-70,-256,-727,576,160,879,-79,-407,312,390,271,120,-971,187,123,-493,-709,56,-662,640,-736,696,399,372,-37,-942,-552,-403,-59,-615,990,547,483,-418,169,-215,-10,-612,581,-438,426,85,449,-762,-652,3,145,491,-649,-602,-560,-874,-698,-236,919,486,835,-769,56,-717,-315,-759,351,-315,993,498,177,-598,-800,-471,346,-91,-283,974,-756,-735,864,-52,98,931,-749,658,-352,727,811,-987,-429,-968,98,-198,-473,-275,167,-8,-688,-845,-39,-455,-415,360,-831,-29,750,-977,287,439,353,-976,-344,-563,-677,209,-292,377,476,-564,-863,-34,-521,138,15,-884,91,-949,627,947,516,95,-690,532,-448,-875,-40,406,316,891,115,-566,-701,-848,126,763,-127,489,516,-297,701,756,-308,372,871,841,369,-83,653,-711,698,-2,-337,239,2,643,-608,-483,-265,-340,800,-285,7,886,-99,548,590,11,-726,-379,57,-909,627,-633,-641,-4,-390,438,328,-925,-796,900,-679,-850,-384,287,-428,972,467,230,-8,164,986,54,776,-220,-573,-262,-726,-152,-696,-504,126,73,691,-712,759,-451,-309,-393,-679,199,443,-146,963,517,958,-217,-205,430,809,-538,13,590,334,-554,-766,554,460,45,-413,693,-67,204,853,362,-859,-214,-252,-438,-345,927,666,250,-101,-931,-235,495,927,-907,900,300,-361,846,-544,-541,158,-804,-249,164,952,-12,898,-428,-375,373,-611,20,789,144,-358,365,371,-879,-205,-495,-868,827,-213,976,283,-178,-402,-822,-256,553,326,-219,169,-176,630,-303,-809,-151,-603,511,304,540,-806,721,-145,713,600,-748,881,-964,3,942,854,-704,112,843,132,78,-833,377,-3,-941,-685,689,663,-986,-206,736,407,-709,763,-627,798,-933,58,-347,29,9,-373,445,852,40,-66,-46,-248,58,-157,-852,-906,269,-769,-547,-157,218,70,892,197,27,-231,534,705,275,67,680,872,-418,-565,121,405,-895,-437,-182,-441,902,-292,389,24,-145,879,-954,-404,464,-39,-644,988,-860,-240,733,-573,-734,901,309,-247,18,798,635,101,995,971,-99,-889,750,13,-864,-496,329,-634,533,902,-962,-423,-479,-955,236,388,767,-873,-545,-980,-430,923,118,774,-592,-516,27,890,-231,-169,-203,-988,-295,571,271,309,-95,-247,745,-259,-174,406,432,-786,-679,-323,305,896,-110,755,43,-335,-341,281,655,433,7,-966,-948,346,542,-423,-107,475,625,-14,79,426,887,791,-663,783,133,924,486,314,156,415,-532,496,-399,-982,843,239,249,-64,653,-206,-748,-492,-916,-950,403,444,-301,739,-228,-468,-599,-390,57,47,-471,-302,-847,-841,-922,-297,33,-709,-210,-454,-831,-527,-659,-360,-359,196,-448,-255,-337,255,727,-274,-354,-627,-870,-167,760,-948,-715,-476,556,544,-766,636,784,882,335,-583,187,-772,-183,76,737,-59,272,-41,-556,72,852,-83,-866,-366,785,900,998,204,-642,124,-866,-858,288,-167,96,-577,-12,117,448,-666,-207,-749,-475,508,586,-221,-525,123,-166,7,-343,-253,-408,-515,523,-290,691,182,-936,-469,-30,-1,136,150,-739,464,176,970,-664,408,87,90,-95,38,330,880,-918,146,-282,477,-612,202,765,110,605,965,-675,580,-423,868,515,-766,-997,967,-844,85,-868,347,-949,-415,-754,664,51,128,-684,15,112,462,-480,-226,-597,-607,73,660,-502,-139,-540,859,-105,146,-407,675,-334,-307,-466,550,-51,471,223,-846,47,-400,20,822,204,-343,894,-152,-347,582,-791,-330,-36,890,521,-620,-87,339,-558,-117,647,54,217,911,475,-737,337,-572,-50,476,-194,160,507,947,658,-761,-115,-442,675,93,509,-351,195,16,-69,459,-643,454,-582,728,-629,461,810,634,208,-671,-964,-524,674,918,-159,-105,-427,473,-477,-719,-306,-539,517,442,894,125,320,-443,-593,364,503,-936,-670,651,-601,-586,502,-572,-873,457,647,747,940,-358,549,333,-387,-448,533,809,-180,856,-437,772,-325,910,981,511,-841,-315,496,458,26,324,245,596,189,25,-938,407,293,-734,-703,202,-528,802,-362,-202,-233,312,14,-593,132,-301,-783,-355,272,-740,-180,742,64,429,716,-40,-779,627,-713,935,-428,325,-774,578,-67,-45,670,-499,-781,314,941,519,132,-729,-288,-386,404,272,-963,-517,-932,172,953,711,951,596,-243,270,124,-205,981,-305,334,-16,-815,680,909,405,-828,-692,970,13,858,-607,118,-663,438,-839,717,605,108,149,714,-842,435,569,-58,563,105,-195,-875,-484,589,-584,526,-727,939,871,304,997,-913,543,878,-490,-317,465,284,-968,206,317,-372,-12,729,662,-925,-373,-537,652,-393,468,602,483,771,453,290,366,-28,473,748,-840,589,946,-923,869,-933,-599,-546,140,-517,-596,822,4,491,606,37,-889,-245,-773,-841,-34,158,563,239,-144,-468,-722,-151,-88,-576,-864,-959,-615,-599,-602,-934,181,978,564,612,-483,-104,-354,943,-714,132,496,182,562,-861,513,-471,-303,-830,-717,705,99,814,-415,-69,-864,-63,-375,427,176,-151,586,-211,-322,91,-870,302,-70,941,-891,-991,875,-827,-557,795,-734,58,612,-337,-122,115,-612,-358,-278,-603,417,770,564,-892,854,-512,-816,482,-192,-52,370,-871,15,795,-389,758,-518,-944,932,-333,889,161,786,-113,-7,-928,-98,792,-579,310,554,305,-18,999,876,-292,584,19,332,360,392,-636,490,425,-967,-959,183,753,819,-583,126,937,494,-312,-991,470,918,78,488,-915,678,353,956,101,-937,151,-905,118,-110,-838,962,-154,664,686,437,-618,-384,-300,130,664,195,-259,-752,952,-343,144,-916,-910,-272,12,-222,-60,869,183,71,-915,-350,-608,-712,180,314,-521,353,273,578,723,-624,-482,-156,-433,157,-735,-431,-22,512,-920,-615,582,129,58,-881,-530,-627,-238,65,-929,65,-256,-664,346,858,-975,544,-410,-9,-485,146,-128,-96,-405,422,-112,20,-611,702,943,983,-667,965,-171,-950,-942,-528,-484,615,-149,-777,891,80,-473,-866,806,-633,168,386,810,-421,-755,911,560,899,-572,865,-445,902,-517,134,-165,373,842,263,-653,-777,497,-514,431,95,990,271,-405,-908,-931,-118,-966,344,337,-319,-455,-702,811,-99,-466,-909,-487,222,460,-613,794,-74,-393,938,746,479,183,759,-675,-876,-513,-884,-427,704,560,-690,438,303,815,-639,47,-662,-424,-381,-686,-252,-794,-519,41,-222,167,301,802,-18,165,-841,352,-207,924,272,800,-878,603,-989,-96,-402,932,-604,-538,360,-670,-746,-786,-216,-901,22,-550,-72,53,946,-718,-130,488,999,-136,12,578,-15,431,-2,752,-196,-849,676,559,332,-492,843,203,795,-586,-818,-841,-163,200,341,-287,122,39,501,-912,-486,-544,-194,787,797,547,-124,818,-389,774,531,80,524,291,-949,-489,484,-514,641,-98,-419,-165,8,462,-706,211,-903,-233,-279,-782,-476,-690,751,-770,-769,-945,854,462,-557,-708,871,777,771,241,-180,-864,-929,572,656,-75,-160,837,991,23,69,276,31,23,-258,-107,51,992,871,-764,-60,-539,-428,382,15,-23,-790,113,694,619,598,299,896,-697,765,-113,414,-25,773,-52,309,992,232,852,-884,874,-194,836,317,564,-535,-790,763,-183,-430,-830,-961,-142,75,65,395,153,451,-948,606,-913,-80,776,-519,-416,369,-737,-812,616,207,60,853,517,695,274,-870,-578,907,616,-391,-175,-461,792,117,-155,899,823,-98,507,763,-691,-621,964,-237,375,65,315,156,-487,-875,883,114,125,-678,-34,743,-406,-693,-534,-944,208,959,-675,-264,-728,354,-283,-630,1,-440,328,-116,690,89,-618,-709,-247,-368,-567,-698,-811,-317,940,-719,-967,-357,958,-770,-66,-210,-185,728,122,-391,-622,937,255,-833,866,791,525,546,-384,346,-274,636,-560,-722,-924,-946,-523,-159,16,159,238,921,289,-39,902,-482,-548,-94,524,251,15,472,-723,880,307,-16,373,952,-19,-889,-872,-579,-403,73,88,-388,-413,457,953,-235,-791,-942,895,-347,163,216,857,43,-418,626,-760,-898,640,114,-278,-390,651,-988,96,-92,510,-476,770,702,-542,-97,-891,76,-242,-598,-565,-586,-64,-637,-784,70,-798,-808,620,502,-580,-995,604,-933,-135,384,453,-549,-229,-627,-573,-82,-519,-533,-711,-120,-881,-196,-634,-594,-124,258,284,-550,-475,-406,798,-169,103,704,308,77,157,-789,134,142,160,889,90,357,17,639,139,220,351,-975,-903,-692,263,211,814,365,-302,-730,778,-565,815,627,-576,-505,367,-691,144,-860,-488,-79,-117,-918,287,444,91,398,-643,148,-821,-258,799,495,-732,584,920,-332,-261,930,776,130,644,260,-876,-454,112,592,11,-461,230,-707,-565,464,62,-15,872,752,401,896,-669,438,735,313,62,978,532,-353,-61,-55,-877,741,781,-479,-443,-457,260,-942,-286,157,-930,-557,-445,-294,515,-943,-590,749,713,-163,-721,-629,-767,-505,-800,-366,637,468,94,601,508,-592,-666,-786,-367,432,558,-124,-404,113,-886,156,739,306,-941,687,-360,27,-321,52,-84,525,-547,-358,-819,-273,134,-286,-95,835,890,672,-658,-159,347,652,953,-452,257,-308,514,511,845,950,-353,-255,-252,705,573,-334,847,133,460,75,401,-86,131,-714,194,-855,546,-528,-281,828,862,376,-202,-862,14,262,574,675,387,-188,847,-766,981,-339,697,-39,137,-403,-364,-916,909,-378,-81,-346,865,-103,465,-427,-430,-184,172,-560,-937,-216,-957,-925,-446,934,403,-548,879,496,-882,300,-831,443,114,252,-442,972,228,419,693,652,-707,885,946,108,-493,896,-750,-389,-733,233,-541,-894,-363,-581,770,950,580,909,-717,657,-750,-94,-541,199,-534,-552,-810,-825,929,827,-945,458,-710,-745,-896,-123,316,-616,389,-282,-644,-941,431,712,9,-948,845,908,-638,407,-811,501,-541,-986,-95,-927,-43,104,-707,396,947,803,622,-645,-707,935,454,-447,494,893,662,-659,40,-428,796,704,478,316,-170,599,842,568,-61,404,-221,-204,94,-717,-59,79,-424,696,-24,-850,561,473,-911,-850,60,-80,-589,-16,-74,-736,642,59,-143,531,-455,-188,-679,193,852,-769,14,-898,683,-950,338,340,448,-684,-116,31,-101,239,349,712,848,-709,-214,439,634,-494,-90,170,-254,-491,-593,623,179,254,-371,-988,-758,-109,875,552,-574,630,-109,354,-889,776,201,-936,-6,-468,978,-466,783,76,322,-420,764,-194,-292,-788,654,814,962,-826,-817,292,412,899,-261,-729,-365,-42,349,917,428,-855,154,-30,-28,-897,843,-122,811,581,831,180,385,867,-990,400,-717,-773,321,-953,502,-852,-648,46,608,-617,641,947,886,-919,-144,-430,-270,92,27,306,522,-97,-555,485,-651,997,730,-717,533,807,89,829,541,-885,-316,167,414,292,90,792,-804,-757,684,1000,856,983,456,-511,609,-699,-995,457,375,487,480,827,-814,867,-416,-81,202,530,-693,-409,-981,-696,-869,-677,-526,-126,-939,-785,-842,364,429,157,518,-995,-417,457,-556,60,330,-270,850,-487,738,46,475,997,703,-903,328,-662,-185,-564,-284,-767,-720,-103,-585,164,37,909,-772,-192,-479,-238,231,-627,-694,-356,-441,-887,-531,-473,-476,375,-406,-589,-133,75,-320,304,146,185,772,35,-538,-306,-633,-730,-423,834,-235,735,993,902,-11,-385,889,-343,-116,505,673,757,738,453,-408,42,-849,-726,586,461,-83,744,-439,962,542,-420,-192,-20,-494,70,114,-397,984,-306,84,43,-599,-860,543,-949,-78,335,-785,156,-909,896,145,-602,584,-681,359,227,-868,717,-923,508,-730,-801,714,557,-133,602,301,574,839,-938,-426,589,329,201,-754,-670,337,292,-416,134,651,325,-263,42,-588,807,108,-316,128,-314,-225,158,415,-208,-913,-433,586,-992,536,-802,-480,-628,-784,-73,-515,908,-34,-269,-37,46,-123,-320,727,443,-381,-647,-715,-427,-788,910,275,-143,-722,568,743,11,265,-459,-266,-122,68,189,228,-306,-463,-113,488,-633,479,-875,909,916,-947,956,-562,-984,-327,-473,-90,-48,131,-179,97,-450,-788,-482,832,413,-35,-857,24,124,-850,788,9,170,-86,400,685,763,-543,-595,-175,-793,171,165,770,117,801,289,942,81,-566,-751,-449,448,220,202,908,-833,-190,537,-425,262,966,-622,883,-714,494,284,-621,218,609,-663,-883,912,-689,287,321,42,-874,-983,423,809,-205,586,-27,-263,-958,541,-66,437,-159,374,729,83,311,-639,443,-627,698,852,-231,56,-322,-922,223,-839,-510,586,-143,-107,203,792,413,62,-543,-858,913,-895,-78,465,810,67,-450,969,-463,-253,952,-583,-787,1000,312,-572,-503,-948,737,-592,-911,-547,-516,671,887,352,439,-187,-830,-21,102,-355,-219,-981,805,885,242,-667,567,755,984,13,-817,732,915,-746,733,684,-971,-374,-60,-861,43,204,970,-988,-945,394,143,-763,743,482,456,47,523,469,-862,-53,-939,562,-784,973,-292,-854,-176,-459,633,75,-358,623,-309,-867,125,-860,-936,46,172,61,-707,-172,-432,-646,179,-874,752,-541,-461,656,-596,507,354,-78,414,-364,756,-902,-294,534,-370,-748,-525,-718,-738,-67,319,-381,-408,278,-581,717,-87,90,-705,-244,-296,-576,724,360,529,-686,285,-305,-169,-977,-20,-940,872,352,79,823,328,630,973,-474,-350,981,-956,-386,-99,334,754,-613,-165,-220,627,775,140,-61,-389,-61,-575,-836,30,952,503,909,-524,-893,-656,-487,-206,-379,-699,355,-76,340,645,-195,-117,675,-389,-720,-26,-118,-587,-876,-815,620,848,944,513,-799,-220,-895,835,40,966,806,768,474,-62,-569,900,81,-438,-853,-246,98,-749,866,640,413,-766,983,-885,636,-969,-144,-949,341,-714,-556,-134,-759,-496,-202,750,894,-300,-178,610,-450,8,70,403,13,-824,25,578,-740,456,-291,-479,-125,-512,950,734,524,657,624,67,-695,-887,964,-472,-45,435,-827,308,772,-897,-242,533,320,-667,-538,-430,-477,537,376,318,410,-456,946,976,-116,-78,368,439,685,724,310,75,711,-808,524,104,398,821,503,-731,151,236,201,-106,680,-786,-318,-2,-394,-665,-564,-191,-813,300,882,-375,-723,577,872,-209,-843,-259,684,472,-358,-118,-903,-480,-162,-140,199,10,849,547,974,-77,-589,-513,-54,-339,645,672,734,587,-896,693,91,-536,-465,-370,-738,119,-409,-1000,-327,991,-167,-971,-939,797,-578,-142,-890,750,238,-966,-218,-54,-672,-337,-887,-111,-400,-167,545,15,78,325,635,-740,342,520,-408,326,-360,369,-638,84,594,-739,304,235,415,-771,310,-454,722,669,845,879,265,-714,-797,-309,857,-477,332,-706,942,-530,-970,364,543,918,-688,-436,200,-729,-544,801,-248,238,167,-315,-556,711,-137,589,835,912,-326,-783,392,-378,-24,811,454,-707,-634,509,-124,-153,-168,261,607,543,918,-922,745,697,86,-411,-902,-570,88,-474,-469,-239,553,349,782,-958,-423,311,-736,-212,544,-874,-969,-166,-54,-927,-527,-859,-880,334,741,365,-776,74,904,-464,96,-200,595,798,-740,967,426,561,574,-603,658,4,-568,565,492,444,71,-589,-219,298,-298,-973,66,989,988,989,-561,12,-977,488,138,-144,-900,-797,899,96,-857,19,479,-696,-741,246,295,-332,-84,-889,315,-971,-932,303,-238,-904,385,-254,227,-336,999,-159,-728,-860,615,-216,-734,-304,-346,572,-94,-624,-179,-341,-746,414,-471,-741,365,-368,-747,120,21,22,847,-967,499,638,-459,929,416,262,668,317,820,-927,-851,399,-845,-14,-780,-202,-814,-549,255,69,-435,-254,-463,908,-758,-290,21,741,-525,-892,191,-160,485,348,-43,-776,670,-66,-310,618,-7,386,-761,125,322,318,724,324,929,359,-377,972,-256,-976,431,373,-725,-204,977,411,-84,767,-413,492,-575,-824,756,-844,242,624,-861,-192,-331,767,-32,484,-571,-685,-838,-320,643,838,-29,-561,236,-757,597,555,667,893,818,-99,107,-113,-587,-477,263,193,247,79,177,992,-820,900,237,-914,-638,-698,-357,267,-662,146,824,-947,-729,-715,486,138,-661,405,942,714,-594,476,757,980,-242,-792,-195,-407,-613,782,963,-981,611,-286,-147,-819,524,-162,873,-203,-562,-381,997,731,-937,-552,160,-480,-691,-219,513,995,754,228,397,-998,229,-221,-738,346,641,372,421,140,-970,-672,532,914,142,259,-296,-883,727,-372,-976,-825,86,257,-798,52,196,-109,582,-218,59,-829,79,-218,747,-666,-813,671,333,388,-56,-205,250,-200,81,-629,-957,10,592,-17,-800,-395,-596,413,-340,617,-658,493,-806,-565,12,637,155,754,525,187,235,-736,328,457,660,765,497,-55,759,-5,259,580,924,26,-402,-50,610,82,-167,-4,-964,535,965,-571,936,-663,-753,714,-5,449,-587,-541,146,260,-165,267,356,-365,-922,-881,420,322,971,931,920,55,672,-13,637,232,805,-583,595,170,-146,-602,-97,-93,-321,-885,937,-634,-150,608,-118,-902,-142,927,-238,-164,-279,597,986,159,403,858,549,-41,343,23,717,793,760,612,418,-811,-834,543,65,-235,688,-897,-622,-743,-67,-319,595,193,899,-785,715,-647,160,652,579,240,690,-971,-377,-294,425,-285,-786,-238,-761,747,-649,489,-885,-551,-656,-835,627,-767,-191,-620,-759,700,-597,279,78,561,987,61,231,-105,-927,277,-868,483,488,293,43,559,-992,-769,770,769,738,-797,-867,955,608,763,58,335,-659,-461,763,-758,-688,863,-76,653,76,427,603,231,-724,907,502,751,-559,-98,-946,639,-259,-251,888,-244,61,383,73,-215,369,-700,-879,-244,-867,659,349,194,310,-732,794,355,-535,-643,161,179,-56,-286,-360,-426,-24,334,171,-541,978,-247,407,909,618,-623,618,-859,-936,365,414,320,469,451,-561,-107,-727,-119,-745,-167,-421,474,642,28,496,-763,-546,-138,167,521,-796,196,-11,-143,-186,-500,-312,482,-550,77,796,998,611,-196,191,-479,-393,-367,301,-381,699,-458,-787,-635,-928,-87,581,865,234,276,138,359,-687,-238,-349,-689,286,41,43,383,680,-688,893,450,346,492,400,187,467,-392,891,681,-435,985,88,162,921,984,333,-429,583,-104,-434,415,785,367,234,908,-740,948,-509,-504,701,-557,-564,698,463,820,-246,-390,400,-815,870,-517,575,-940,290,-875,332,315,-308,-562,343,-344,-549,-63,-343,816,254,63,523,922,-256,457,950,17,247,221,-563,172,123,511,-452,-750,-91,-217,-795,-679,463,-198,526,-977,-533,582,59,107,-403,-752,968,31,-351,757,746,170,-93,809,295,318,-951,938,-681,-725,468,-387,-820,905,-153,568,-252,-696,761,-854,-113,271,547,-766,-860,-390,749,-39,-778,-846,-783,837,751,-166,-591,-149,-922,-126,-974,-784,-774,-166,210,-273,-811,923,-7,721,-229,-964,-29,650,39,-939,765,-175,-231,203,476,-832,459,979,955,-754,-241,-657,-99,-563,857,-777,-768,-10,-33,518,-801,542,513,254,69,582,711,-361,990,348,875,-280,237,-226,552,630,76,908,-497,683,-745,-555,-418,-561,-676,-397,-238,767,565,-996,-225,-850,494,652,60,874,366,638,-561,-645,718,240,501,591,387,-633,125,550,727,161,-129,813,976,-284,85,-578,-937,156,502,-10,-1,-140,-594,-711,960,567,72,-822,-373,145,131,410,137,-972,301,-1000,829,-762,915,270,-81,173,-829,359};
        int[] arr={-1,-1,-1,0,1,1};
//        int[] arr={1,2,3};
//        int[] arr = {-1, -1, -1, -1, -1, -1};
//        int[] arr = {-1, 0, 1, -1, -1, -1};
//        int[] arr={1,7,3,6,5,6};
        System.out.println(pivotIndex(arr));
    }

    public static int pivotIndex(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        int p = n % 2;
        int num1 = 0;
        int num2 = 0;
        for (int i = 0; i < n; i++) {
            System.out.println("i="+i+"===========");
            num1 = 0;
            for (int j = i-1;  j >= 0; j--) {
                num1 += nums[j];
                System.out.println("num1,j="+j+",num1="+num1);
            }
            num2 = 0;
            for (int j = i+1; j < n; j++) {
                num2 += nums[j];
                System.out.println("num2,j="+j+",num2="+num2);
            }
            if (num1 == num2) {
                return i;
            }
        }
        return -1;
    }

    /**
     * LeetCode大神的最优解
     * @param nums
     * @return
     */
    public static int pivotIndex1(int[] nums) {
        //求出nums的总和
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            sum += num;
        }
        //另一边的总和
        int tmpSum = 0;
        for (int i = 0; i < nums.length; i++) {
            //总和减去tmpSum，再减去nums[i]，若等于tmpSum就代表i的左右之和相等，则返回i
            if (tmpSum == sum - tmpSum - nums[i]) {
                return i;
            }
            tmpSum += nums[i];
        }
        return -1;
    }
}
